// 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

// 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

// 你可以返回任何满足上述条件的数组作为答案。

//  

// 示例：

// 输入：[4,2,5,7]
// 输出：[4,5,2,7]
// 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
//  

// 提示：

// 2 <= A.length <= 20000
// A.length % 2 == 0
// 0 <= A[i] <= 1000

#include <vector>

using namespace std;

// 开辟新的数组，空间复杂度O(n) 时间复杂度O(n)
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int n = A.size();
        vector<int> res(n, 0);
        int even{0};
        int odd{1};
        for (int i{0}; i < n; ++i) { // i 表示奇数，j表示偶数
            if (A[i] % 2 == 0) {
                res[even] = A[i];
                even += 2;
            } else if (A[i] % 2 != 0) {
                res[odd] = A[i];
                odd += 2;
            }
        }
        return res;
    }
};

/* 原地修改
为数组的偶数下标部分和奇数下标部分分别维护指针 i,j。随后，在每一步中，如果 A[i] 为奇数，则不断地向前移动 j（每次移动两个单位），直到遇见下一个偶数。此时，可以直接将 A[i] 与 A[j] 交换。我们不断进行这样的过程，最终能够将所有的整数放在正确的位置上。
*/
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int n = A.size();
        int j = 1; // j 是奇数下标
        for (int i = 0; i < n; i += 2) { // i 是偶数下标
            if (A[i] % 2 == 1) { // 只在A[i]是奇数的时候进行处理
                while (A[j] % 2 == 1) { // 寻找奇数位上的第一个偶数
                    j += 2;
                }
                swap(A[i], A[j]);
            }
        }   
        return A;
    }
};